package com.yun.algorithmproblem.leetcode;

public class Leetcode3356 {

    public static void main(String[] args) {
        Leetcode3356 leetcode3356 = new Leetcode3356();
        // 初始化 nums 数组
        int[] nums = {2, 0, 2};

        // 初始化 queries 数组
        int[][] queries = {
                {0, 2, 1},  // 更新区间 [0, 2]，减去 1
                {0, 2, 1},  // 更新区间 [0, 2]，减去 1
                {1, 1, 3}   // 查询区间 [1, 1] 的和
        };
        int i = leetcode3356.minZeroArray(nums, queries);
        System.out.println(i);
    }

    /**
     * 思路: 用线段树,新建一个数组,计算queries相加,最后新数组和老数组对比
     */
    public int minZeroArray(int[] nums, int[][] queries) {
        SegmentTree segmentTree = new SegmentTree(nums);
        int n = segmentTree.n;
        if (segmentTree.tree[0] == 0) {
            return 0;
        }
        for (int i = 0; i < queries.length; i++) {
            segmentTree.update(0, 0, n - 1, queries[i][0], queries[i][1], queries[i][2]);
            if (segmentTree.tree[0] == 0) {
                return i + 1;
            }
        }
        return -1;
    }

    private static class SegmentTree {
        private int[] tree;  // 线段树的数组表示
        private int[] lazy;  // 懒标记树
        private int n;  // 数组大小

        public SegmentTree(int[] nums) {
            n = nums.length;
            tree = new int[4 * n];  // 线段树的大小是 4 * n
            lazy = new int[4 * n];  // 初始化懒标记数组
            build(nums, 0, 0, n - 1);  // 构建线段树
        }

        // 构建线段树
        private void build(int[] nums, int node, int start, int end) {
            if (start == end) {
                tree[node] = nums[start];
            } else {
                int mid = (start + end) >> 1;
                int leftChild = 2 * node + 1;
                int rightChild = 2 * node + 2;
                build(nums, leftChild, start, mid);
                build(nums, rightChild, mid + 1, end);
                tree[node] = Math.max(tree[leftChild], tree[rightChild]);
            }
        }

        // 更新区间
        public void update(int node, int start, int end, int l, int r, int val) {
            if (l <= start && end <= r) {
                tree[node] = Math.max(0, tree[node] - val);
                lazy[node] += val;
                return;
            }
            int mid = (start + end) >> 1;
            pushDown(node, mid - start + 1, end - mid);
            int leftChild = 2 * node + 1;
            int rightChild = 2 * node + 2;
            //更新左右的节点
            if (l <= mid) {
                update(leftChild, start, mid, l, r, val);
            }
            if (r > mid) {
                update(rightChild, mid + 1, end, l, r, val);
            }
            //更新当前区间的值
            pushUp(node);
        }

        // 查询区间 [l, r] 的最大值
        public int query(int node, int start, int end, int l, int r) {
            if (r < start || end < l) {
                return 0;  // 不在查询范围内
            }
            if (l <= start && end <= r) {
                return tree[node];  // 完全在查询范围内
            }
            int mid = (start + end) / 2;
            pushDown(node, mid - start + 1, end - mid);
            int leftChild = 2 * node + 1;
            int rightChild = 2 * node + 2;
            int leftQuery = query(leftChild, start, mid, l, r);
            int rightQuery = query(rightChild, mid + 1, end, l, r);
            return Math.max(leftQuery, rightQuery);
        }

        private void pushUp(int node) {
            int leftChild = 2 * node + 1;
            int rightChild = 2 * node + 2;
            tree[node] = Math.max(tree[leftChild], tree[rightChild]);
        }

        private void pushDown(int node, int leftNum, int rightNum) {
            int leftChild = 2 * node + 1;
            int rightChild = 2 * node + 2;
            if (lazy[node] == 0) {
                return;
            }
            tree[leftChild] = Math.max(0, tree[leftChild] - lazy[node]);
            tree[rightChild] = Math.max(0, tree[rightChild] - lazy[node]);
            lazy[leftChild] += lazy[node];
            lazy[rightChild] += lazy[node];
            lazy[node] = 0;
        }
    }
}
